Run Fixup on the database - this will force a consistency check. Or justr have the user restart their Notes client - this should also force it.
Of course, if the mailfile is large, this could take several hours - anoth argument for users to keep their mailfile size down.
Check this, from the Notes Admin Help:
When you restart a server, the server quickly searches for any unlogged databases that were modified but improperly closed because of a server failure, power failure, hardware failure, and so on. A few minutes after server startup is complete, the Fixup task then runs on these databases to attempt to fix any inconsistencies that resulted from partially written operations caused by a failure. When users attempt to access one of these databases and Fixup hasn't yet run on the database, the users see the message "This database cannot be opened because a consistency check of it is in progress." A similar Fixup process occurs when you restart a Lotus Notes client.
Stephen Lister